package PersonStu.sanqi;

/**
 * @Author: Dijah
 * @Date: 2022/7/26 16:50
 * @Desc: kmp算法
 */
public class class02_kmp {

    public static int getIndexOf(String s,String m){
        if(s == null || m == null || s.length() < 1 || m.length() < 1 || m.length() > s.length()){
            return -1;
        }
        char [] str1 = s.toCharArray();
        char [] match = m.toCharArray();

        int x = 0;//str中当前比对到的位置
        int y = 0;//match中当前比对的位置

        int [] next = getNextArray(match);//next[i] match中i之前的字符串match[0...i-1]
        while (x < str1.length  && y < match.length){
            if(str1[x] == match[y]){
                //x的位置等于y的位置，那么就比较下一个位置
                x++;
                y++;
            }else if(next[y] == -1){ //y=0
                //如果当前的位置不等,在string的位置中换一个位置你去++吧。
                x++;
            }else{
                //
                y = next[y];
            }
        }
        return y == match.length ? x-y : -1;
    }

    /**
     *
     * @param str2:要匹配的字符串
     * @return 时间复杂度：O(n)
     */
    private static int[] getNextArray(char[] str2) {
        if(str2.length == 1){
            return new int[]{-1};
        }
        int [] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;

        //cn：表示最长前缀的那个长度，也表示当前的这个位置和i-1位置比较的字符
        int cn = 0;
        while (i < next.length){
            if(str2[i-1] == str2[cn]){ //跳出来的时候
                //如果匹配的上，那么进行下一位匹配
//                next[i] = cn+1;
//                i++;
//                cn++;

                next[i++] = ++cn;
            }else if(cn > 0){
                //说明cn还能往前跳
                cn = next[cn];
            }else {
                //跳到开头了，也没有一个相等的
                next[i++] = 0;
            }
        }
        return next;
    }



    public static void main(String[] args) {
//        int indexOf = getIndexOf("asdfrtyrtyrty", "yrty");
//        System.out.println(indexOf);"mississippi"
//"issipi"
        int i = getIndexOf("qaacbtaacbs", "aacbaacbs");
        System.out.println(i);
    }
}
